Computing Regions Decomposable into m Stars

Matt Gibson; Kasturi Varadarajan; Xiaodong Wu

doi:10.1007/978-3-662-44777-2_40

Back

Computing Regions Decomposable into m Stars

Book chapter

Peer reviewed

Computing Regions Decomposable into m Stars

Matt Gibson, Kasturi Varadarajan and Xiaodong Wu

Algorithms - ESA 2014, pp.480-491

Lecture Notes in Computer Science, Springer Berlin Heidelberg

2014

DOI: 10.1007/978-3-662-44777-2_40

View Online

Abstract

Motivated by an approach to image segmentation, we consider an optimization problem on a node-weighted planar grid graph, that of finding a maximum weight subset of nodes that can be partitioned into m subsets, each with a simple geometric structure. The problem has been considered in earlier papers, which give polynomial time algorithms for m = 2. We show that the problem admits a polynomial time algorithm for any fixed m ≥ 3.

Grid Cell

Grid Node

Polynomial Time Algorithm

Span Tree

Voronoi Diagram

Details

Title: Subtitle: Computing Regions Decomposable into m Stars
Creators: Matt Gibson - University of Texas at San Antonio
Kasturi Varadarajan - University of Iowa
Xiaodong Wu - University of Iowa
Resource Type: Book chapter
Publication Details: Algorithms - ESA 2014, pp.480-491
Publisher: Springer Berlin Heidelberg; Berlin, Heidelberg
Series: Lecture Notes in Computer Science
DOI: 10.1007/978-3-662-44777-2_40
eISSN: 1611-3349
ISSN: 0302-9743
Language: English
Date published: 2014
Academic Unit: Electrical and Computer Engineering; Radiation Oncology; The Iowa Institute for Biomedical Imaging; Computer Science
Record Identifier: 9984197229802771

Metrics

14 Record Views