Centers of sets of pixels

Samir Khuller; Azriel Rosenfeld; Angela Wu

doi:10.1016/S0166-218X(99)00248-6

Centers of sets of pixels

Samir Khuller^*, Azriel Rosenfeld, Angela Wu

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

The center of a connected graph G is the set of nodes of G for which the maximum distance to any other node of G is as small as possible. If G is a simply connected set of lattice points ("pixels") with graph structure defined by 4-neighbor adjacency, we show that the center of G is either a 2×2 square block, a diagonal staircase, or a (dotted) diagonal line with no gaps.

Original language	English (US)
Pages (from-to)	297-306
Number of pages	10
Journal	Discrete Applied Mathematics
Volume	103
Issue number	1-3
DOIs	https://doi.org/10.1016/S0166-218X(99)00248-6
State	Published - Jul 15 2000

Keywords

Center
Chessboard distance
City block distance
Intrinsic distance
Simply connected set

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/S0166-218X(99)00248-6

Cite this

@article{8b213e55635f4fcd881437f139ac75a7,

title = "Centers of sets of pixels",

abstract = "The center of a connected graph G is the set of nodes of G for which the maximum distance to any other node of G is as small as possible. If G is a simply connected set of lattice points ({"}pixels{"}) with graph structure defined by 4-neighbor adjacency, we show that the center of G is either a 2×2 square block, a diagonal staircase, or a (dotted) diagonal line with no gaps.",

keywords = "Center, Chessboard distance, City block distance, Intrinsic distance, Simply connected set",

author = "Samir Khuller and Azriel Rosenfeld and Angela Wu",

note = "Funding Information: The authors thank Fridrich Sloboda for suggesting the problem, Reinhard Klette for early discussions, and Janice Perrone for her help in preparing this paper. The first author's research is supported by NSF Career Award CCR 95-01355.",

year = "2000",

month = jul,

day = "15",

doi = "10.1016/S0166-218X(99)00248-6",

language = "English (US)",

volume = "103",

pages = "297--306",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Centers of sets of pixels

AU - Khuller, Samir

AU - Rosenfeld, Azriel

AU - Wu, Angela

N1 - Funding Information: The authors thank Fridrich Sloboda for suggesting the problem, Reinhard Klette for early discussions, and Janice Perrone for her help in preparing this paper. The first author's research is supported by NSF Career Award CCR 95-01355.

PY - 2000/7/15

Y1 - 2000/7/15

N2 - The center of a connected graph G is the set of nodes of G for which the maximum distance to any other node of G is as small as possible. If G is a simply connected set of lattice points ("pixels") with graph structure defined by 4-neighbor adjacency, we show that the center of G is either a 2×2 square block, a diagonal staircase, or a (dotted) diagonal line with no gaps.

AB - The center of a connected graph G is the set of nodes of G for which the maximum distance to any other node of G is as small as possible. If G is a simply connected set of lattice points ("pixels") with graph structure defined by 4-neighbor adjacency, we show that the center of G is either a 2×2 square block, a diagonal staircase, or a (dotted) diagonal line with no gaps.

KW - Center

KW - Chessboard distance

KW - City block distance

KW - Intrinsic distance

KW - Simply connected set

UR - http://www.scopus.com/inward/record.url?scp=0347934506&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347934506&partnerID=8YFLogxK

U2 - 10.1016/S0166-218X(99)00248-6

DO - 10.1016/S0166-218X(99)00248-6

M3 - Article

AN - SCOPUS:0347934506

SN - 0166-218X

VL - 103

SP - 297

EP - 306

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

Centers of sets of pixels

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this